package com.LeeCode;

import java.util.Arrays;

/**
 * 最短匹配子字符串
 */

public class Code3363 {
    public static void main(String[] args) {

    }

    public int maxCollectedFruits(int[][] fruits) {
        int n = fruits.length;
        int[][] memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }

        int ans = 0;
        // 从 (0, 0) 出发的小朋友
        for (int i = 0; i < n; i++) {
            ans += fruits[i][i];
        }

        // 从 (0, n - 1) 出发的小朋友（倒着走）
        // 从下往上走，方便 1:1 翻译成递推
        ans += dfs(n - 2, n - 1, fruits, memo);

        // 从 (n - 1, 0) 出发的小朋友（按照主对角线翻转，然后倒着走）
        // 把下三角形中的数据填到上三角形中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                fruits[j][i] = fruits[i][j];
            }
        }
        for (int[] row : memo) {
            Arrays.fill(row, -1); // -1 表示没有计算过
        }
        return ans + dfs(n - 2, n - 1, fruits, memo);
    }

    private int dfs(int i, int j, int[][] fruits, int[][] memo) {
        int n = fruits.length;
        if (j < n - 1 - i || j >= n) {
            return 0;
        }
        if (i == 0) {
            return fruits[i][j];
        }
        if (memo[i][j] != -1) { // 之前计算过
            return memo[i][j];
        }
        int res1 = dfs(i - 1, j - 1, fruits, memo);
        int res2 = dfs(i - 1, j, fruits, memo);
        int res3 = dfs(i - 1, j + 1, fruits, memo);
        int res = Math.max(Math.max(res1, res2), res3) + fruits[i][j];
        return memo[i][j] = res; // 记忆化
    }
}
